The present invention relates to storage of data in a memory and, more particularly, to the order in which a stream of incoming data is stored in a non-volatile memory.
Examples of the storage of streams of data include the recording of digital audio (such as MP3 music files) in a cellular phone, the recording of digital video in a digital video camera, the recording of one or more digital still pictures in a digital still camera, and the copying of files from a personal computer into a portable USB flash drive. In all such cases the system contains a non-volatile memory module (that may be a flash memory card, a USB flash drive, an embedded on-board flash memory chip or any other configuration supporting non-volatile storage) and a data source that provides the data to be stored as a sequence of fixed-size sectors (in this application the term “sector” denotes a fixed-size chunk of data that is used as a basic unit of data exchange between the data source and the memory module). The data source may be the CPU controlling the camera or the cellular phone, the CPU of a host computer retrieving previously stored data from its hard disk and sending the data to the portable USB drive, the controller of a sensor collecting image data, or any other component capable of providing a stream of data.
There are cases in which the order of arrival of the data sectors from the data source to the memory module is not the best order for writing the sectors into the memory module.
A first example in which this may be the case is that of storing the data in a way that optimizes the speed of later reading them out. Considerations regarding optimizing reading performance by methods of allocating space inside a memory device are found in Lasser, U.S. patent application Ser. No. 10/952,837, filed on Sep. 30, 2004 and entitled “Method of Managing Files for Optimal Performance”. This patent application is incorporated by reference for all purposes as if fully set forth herein. Such methods are very useful when the data are expected to be read out many times before being deleted or modified, as it is cost-effective to spend more time on re-arranging the data when writing them in return for faster reading that will pay back many times. Copying MP3 music files into a flash memory based MP3 player provides a good example of this: a song will most probably be played back many times before the user will delete it for making room for a new one. Similarly, there are cases in which the reading performance is much more important than the writing performance. For example, a memory module for a game console must launch the game application as fast as possible so as not to annoy the user waiting for the opening screen to appear, while the pre-loading of the game application into the module is done once at manufacturing time. Although the specific examples in U.S. Ser. No. 10/952,837 do not require storage in a diferent order from that in which the data are received, systems are known in which data are received in one order and presented to a user in a different order. For example, Birk et al., U.S. Pat. No. 6,502,139, teach a Near Video On Demand method in which the segments of a video stream are all transmitted simultaneously, with the segments subsequent to the first segment being broken into subsegments before transmission, and the later subsegments of a segment subsequent to the first segment may be received by a viewer before the earlier subsegments of the same segment. A viewer wishing to archive such a video transmission needs to re-order the segments and the subsegments in order to store them in their true order. To summarize this example: a sequence of sectors is provided by a data source to a memory module, such that each sector of data requires one writing operation in order to be stored, and it is desired that the order in which the sectors are stored in memory be different from the order in which the sectors are originally received. In some memory technologies it is possible to implement the required order permutation by writing each sector, upon its arrival, into its final target location. However, many memory technologies do not allow random order of writing. For example Multi-Level-Cell (MLC) NAND flash devices require the physical pages of a memory unit to be written strictly sequentially, and therefore the desired re-ordering of the sectors must be done after the whole group of permuted sectors targeted for the same memory unit is available, so that the writing can proceed sequentially in the physical space and still produce the desired storage order.
Other examples of the need to change the order of writing operations (as compared with the order of receiving the data sectors) are more complex, as they lack the simple one-to-one correspondence between a sector and a write operation. This complication may arise with storage technologies that require one or more of the sectors to be written more than once. See for example Chen et al. U.S. Pat. No. 6,522,580 entitled “Operating Techniques For Reducing Effects Of Coupling Between Storage Elements Of a Non-Volatile Memory Operated in Multiple Data States”. This patent is incorporated by reference for all purposes as if fully set forth herein. U.S. Pat. No. 6,522,580 teaches a method for eliminating or reducing cross-coupling effects between flash memory cells that store two bits per cell. The method requires that some of the data sectors be written a second time after other sectors are written to neighboring cells. See for example claim 1 of U.S. Pat. No. 6,522,580 that recites writing “a first group of storage elements” a second time, and claim 3 that recites that such second writing is not adjacent in time to the first writing of those cells, but is done after the writing of a second group of the storage elements (i.e. after another sector is written to adjacent cells). When using flash memory cells containing higher numbers of bits per cell (for example 4 bits per cell) there are much tougher requirements for reducing cross coupling effects, and therefore the limitations on writing order and on repeating writing more than once become even more complex than in U.S. Ser. No. 622,580. To summarize this example: a sequence of sectors is provided by a data source to a memory module, where each sector of data may require either one or more than one writing operation, and where it is desired that the order of the writing operations (which are now higher in number than the number of data sectors provided by the source, as some sectors are written more than once) be different from the order in which the corresponding sectors were originally received.
The prior art solution for achieving the required re-ordering and/or repeating of the writing operations uses a buffering technique. The incoming data sectors are buffered in a local volatile memory of the controller of the memory module. Then, after all the sectors that comprise the group of sectors that have to be manipulated together are available to the controller in its local volatile memory, the required re-ordering is determined, and a sequence of write operations that obey the restrictions of the non-volatile storage technology is generated. After the sequence ends, the buffered sectors are no longer needed and can be deleted from the volatile memory to make room for new data sectors.
This solution suffers from the following limitations:    a. There is a need for more volatile memory in the controller of the memory module. Usually the controller is a low-performance processing device, as it is highly desirable to reduce its cost. The amount of extra volatile memory required for the above buffering can be quite significant compared to the amount of volatile memory required for other purposes. For example, a low-cost microcontroller may have only 16 Kbytes of internal RAM, while a requirement for buffering 32 sectors of 2 Kbytes each translates into 64 Kbytes of RAM, so in this case a significant increase in the amount of RAM would be required with a corresponding increase in the controller's cost.    b. While the incoming data sectors are buffered in the volatile memory, these sectors are under risk of loss in case of a power failure. Volatile memory, as its name implies, loses its contents when power is removed. So it may be the case that the data source, after sending out a certain number of data sectors, assumes that those sectors are already safely stored in the memory module and therefore can be deleted from the source, while in reality the sectors are still buffered in volatile memory waiting to be stored into nonvolatile memory. The end result might be that an unexpected power loss (e.g. the user shutting the device off) results in a permanent loss of data.    c. Buffering of the data in volatile memory followed by flushing the data into nonvolatile memory might have a negative impact on the system's performance. Because of the risk of data loss described above, the controller typically attempts to flush out the buffered data into safe nonvolatile storage as soon as this is allowable. For example, if the re-ordering requirements lead to the buffering of 32 data sectors (because this is the group of sectors within which re-ordering is to be done), then once 32 sectors are available in the buffer and the flushing of data into the nonvolatile memory can start, the controller writes all of the sectors into their target location. If the writing into the nonvolatile medium is slow, this holds up the memory module in a busy state for a relatively long time and might cause a problem to the data source that may need to provide new data during that time. For example, if the writing of a sector into nonvolatile memory takes one millisecond, then the flushing of a 32-sector buffer takes 32 milliseconds. A digital video camera generating an MPEG2 stream with an average rate of 500 Kbytes per second produces a new sector of 2 Kbytes every 4 milliseconds on average, and cannot accept a pause of 32 milliseconds in the memory's operation.    d. The above considerations all dealt with localized writing, in which the incoming data are all part of one logical sequence and are to be stored together. There are however cases in which the data source simultaneously generates data for two different logical sequences that are to be stored separately. For example, a digital still camera that supports voice narration over a picture may send one stream of picture image data intermixed with a second stream of audio data, such that the two streams are to be stored in different (even though logically linked) files. For the prior art solution to handle such case, the amount of volatile buffering memory must be increased. This is so because each of the streams of sectors must be re-ordered on its own, and therefore each requires its own separate buffer. This further increases the cost of the memory module.
There is thus a widely recognized need for, and it would be highly advantageous to have, a method of re-ordering or repeating writing operations to a memory module that would overcome the disadvantages of the presently known method as described above.